{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Grid Illumination"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: gridIllumination"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #网格照明"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>在大小为 <code>n x n</code> 的网格 <code>grid</code> 上，每个单元格都有一盏灯，最初灯都处于 <strong>关闭</strong> 状态。</p>\n",
    "\n",
    "<p>给你一个由灯的位置组成的二维数组&nbsp;<code>lamps</code> ，其中 <code>lamps[i] = [row<sub>i</sub>, col<sub>i</sub>]</code> 表示 <strong>打开</strong> 位于 <code>grid[row<sub>i</sub>][col<sub>i</sub>]</code> 的灯。即便同一盏灯可能在 <code>lamps</code> 中多次列出，不会影响这盏灯处于 <strong>打开</strong> 状态。</p>\n",
    "\n",
    "<p>当一盏灯处于打开状态，它将会照亮 <strong>自身所在单元格</strong> 以及同一 <strong>行</strong> 、同一 <strong>列</strong> 和两条 <strong>对角线</strong> 上的 <strong>所有其他单元格</strong> 。</p>\n",
    "\n",
    "<p>另给你一个二维数组 <code>queries</code> ，其中 <code>queries[j] = [row<sub>j</sub>, col<sub>j</sub>]</code> 。对于第 <code>j</code> 个查询，如果单元格 <code>[row<sub>j</sub>, col<sub>j</sub>]</code> 是被照亮的，则查询结果为 <code>1</code> ，否则为 <code>0</code> 。在第 <code>j</code> 次查询之后 [按照查询的顺序] ，<strong>关闭</strong> 位于单元格 <code>grid[row<sub>j</sub>][col<sub>j</sub>]</code> 上及相邻 8 个方向上（与单元格 <code>grid[row<sub>i</sub>][col<sub>i</sub>]</code> 共享角或边）的任何灯。</p>\n",
    "\n",
    "<p>返回一个整数数组 <code>ans</code> 作为答案， <code>ans[j]</code> 应等于第 <code>j</code> 次查询&nbsp;<code>queries[j]</code>&nbsp;的结果，<code>1</code> 表示照亮，<code>0</code> 表示未照亮。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/08/19/illu_1.jpg\" style=\"height: 209px; width: 750px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 5, lamps = [[0,0],[4,4]], queries = [[1,1],[1,0]]\n",
    "<strong>输出：</strong>[1,0]\n",
    "<strong>解释：</strong>最初所有灯都是关闭的。在执行查询之前，打开位于 [0, 0] 和 [4, 4] 的灯。第 0&nbsp;次查询检查 grid[1][1] 是否被照亮（蓝色方框）。该单元格被照亮，所以 ans[0] = 1 。然后，关闭红色方框中的所有灯。\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/08/19/illu_step1.jpg\" style=\"height: 218px; width: 500px;\" />\n",
    "第 1&nbsp;次查询检查 grid[1][0] 是否被照亮（蓝色方框）。该单元格没有被照亮，所以 ans[1] = 0 。然后，关闭红色矩形中的所有灯。\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/08/19/illu_step2.jpg\" style=\"height: 219px; width: 500px;\" />\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 5, lamps = [[0,0],[4,4]], queries = [[1,1],[1,1]]\n",
    "<strong>输出：</strong>[1,1]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 5, lamps = [[0,0],[0,4]], queries = [[0,4],[0,1],[1,4]]\n",
    "<strong>输出：</strong>[1,1,0]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>9</sup></code></li>\n",
    "\t<li><code>0 &lt;= lamps.length &lt;= 20000</code></li>\n",
    "\t<li><code>0 &lt;= queries.length &lt;= 20000</code></li>\n",
    "\t<li><code>lamps[i].length == 2</code></li>\n",
    "\t<li><code>0 &lt;= row<sub>i</sub>, col<sub>i</sub> &lt; n</code></li>\n",
    "\t<li><code>queries[j].length == 2</code></li>\n",
    "\t<li><code>0 &lt;= row<sub>j</sub>, col<sub>j</sub> &lt; n</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [grid-illumination](https://leetcode.cn/problems/grid-illumination/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [grid-illumination](https://leetcode.cn/problems/grid-illumination/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['5\\n[[0,0],[4,4]]\\n[[1,1],[1,0]]', '5\\n[[0,0],[4,4]]\\n[[1,1],[1,1]]', '5\\n[[0,0],[0,4]]\\n[[0,4],[0,1],[1,4]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def gridIllumination(self, n, lamps, queries):\n",
    "        point,dic1,dic2,dic3,dic4=dict(),dict(),dict(),dict(),dict()\n",
    "        for A in lamps:\n",
    "            A=tuple(A)\n",
    "            if A not in point:\n",
    "                point[A]=1\n",
    "                dic1[A[0]]=dic1.get(A[0],0)+1\n",
    "                dic2[A[1]]=dic2.get(A[1],0)+1\n",
    "                dic3[A[0]-A[1]]=dic3.get(A[0]-A[1],0)+1\n",
    "                dic4[A[0]+A[1]]=dic4.get(A[0]+A[1],0)+1\n",
    "\n",
    "        ans=list()\n",
    "        print(len(queries),len(point))\n",
    "        for Q in queries:\n",
    "            if dic1.get(Q[0],0)!=0 or dic2.get(Q[1],0)!=0 or dic3.get(Q[0]-Q[1],0)!=0 or dic4.get(Q[0]+Q[1],0)!=0:\n",
    "                ans.append(1)\n",
    "            else:\n",
    "                ans.append(0)\n",
    "            i,j=Q[0],Q[1]\n",
    "            if i>0 and j>0 and point.get((i-1,j-1),0)!=0:\n",
    "                point[(i-1,j-1)]=0\n",
    "                dic1[i-1]-=1\n",
    "                dic2[j-1]-=1\n",
    "                dic3[i-j]-=1\n",
    "                dic4[i+j-2]-=1\n",
    "            if i>0 and point.get((i-1,j),0)!=0:\n",
    "                point[(i-1,j)]=0\n",
    "                dic1[i-1]-=1\n",
    "                dic2[j]-=1\n",
    "                dic3[i-j-1]-=1\n",
    "                dic4[i+j-1]-=1\n",
    "            if i>0 and j<n and point.get((i-1,j+1),0)!=0:\n",
    "                point[(i-1,j+1)]=0\n",
    "                dic1[i-1]-=1\n",
    "                dic2[j+1]-=1\n",
    "                dic3[i-j-2]-=1\n",
    "                dic4[i+j]-=1\n",
    "            if j>0 and point.get((i,j-1),0)!=0:\n",
    "                point[(i,j-1)]=0\n",
    "                dic1[i]-=1\n",
    "                dic2[j-1]-=1\n",
    "                dic3[i-j+1]-=1\n",
    "                dic4[i+j-1]-=1\n",
    "            if point.get((i,j),0)!=0:\n",
    "                point[(i,j)]=0\n",
    "                dic1[i]-=1\n",
    "                dic2[j]-=1\n",
    "                dic3[i-j]-=1\n",
    "                dic4[i+j]-=1\n",
    "            if j<n and point.get((i,j+1),0)!=0:\n",
    "                point[(i,j+1)]=0\n",
    "                dic1[i]-=1\n",
    "                dic2[j+1]-=1\n",
    "                dic3[i-j-1]-=1\n",
    "                dic4[i+j+1]-=1\n",
    "            if i<n and j>0 and point.get((i+1,j-1),0)!=0:\n",
    "                point[(i+1,j-1)]=0\n",
    "                dic1[i+1]-=1\n",
    "                dic2[j-1]-=1\n",
    "                dic3[i-j+2]-=1\n",
    "                dic4[i+j]-=1\n",
    "            if i<n and point.get((i+1,j),0)!=0:\n",
    "                point[(i+1,j)]=0\n",
    "                dic1[i+1]-=1\n",
    "                dic2[j]-=1\n",
    "                dic3[i-j+1]-=1\n",
    "                dic4[i+j+1]-=1\n",
    "            if i<n and j<n and point.get((i+1,j+1),0)!=0:\n",
    "                point[(i+1,j+1)]=0\n",
    "                dic1[i+1]-=1\n",
    "                dic2[j+1]-=1\n",
    "                dic3[i-j]-=1\n",
    "                dic4[i+j+2]-=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def gridIllumination(self, n: int, lamps: List[List[int]], queries: List[List[int]]) -> List[int]:\r\n",
    "        lap = set((x, y) for x, y in lamps)\r\n",
    "        col = Counter()\r\n",
    "        row = Counter()\r\n",
    "        diff = Counter()\r\n",
    "        s = Counter()\r\n",
    "        for x, y in lap:\r\n",
    "            row[x] += 1\r\n",
    "            col[y] += 1\r\n",
    "            diff[x - y] += 1\r\n",
    "            s[x + y] += 1\r\n",
    "        res = []\r\n",
    "        for x, y in queries:\r\n",
    "            if row[x] or col[y] or diff[x - y] or s[x + y]:\r\n",
    "                res.append(1)\r\n",
    "            else:\r\n",
    "                res.append(0)\r\n",
    "            for i in range(-1, 2):\r\n",
    "                for j in range(-1, 2):\r\n",
    "                    if (x + i, y + j) in lap:\r\n",
    "                        row[x + i] -= 1\r\n",
    "                        col[y + j] -= 1\r\n",
    "                        diff[x + i - (y + j)] -= 1\r\n",
    "                        s[x + i + y + j] -= 1\r\n",
    "                        lap.remove((x + i, y + j))\r\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gridIllumination(self, n: int, lamps: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        lamps_light = set()\n",
    "        colnum = dict() # 保存每一列被照亮的个数\n",
    "        rownum = dict() # 保存每一列被照亮的个数\n",
    "        diagnum = dict() # 保存每一左45列被照亮的个数  y-x\n",
    "        diag1num = dict() # 保存每一右45列被照亮的个数 x+y\n",
    "        res = []\n",
    "        for row,col in lamps:\n",
    "            lamps_light.add((row,col))\n",
    "        \n",
    "        for (rowc,colc) in lamps_light:\n",
    "            rownum[rowc] = (rownum[rowc] + 1 if rowc in rownum else 1)\n",
    "            colnum[colc] = (colnum[colc] + 1 if colc in colnum else 1)\n",
    "            diagnum[colc - rowc] = (diagnum[colc - rowc] + 1 if colc - rowc in diagnum else 1)\n",
    "            diag1num[colc + rowc] = (diag1num[colc + rowc] + 1 if colc + rowc in diag1num else 1)\n",
    "\n",
    "        for rowq,colq in queries:\n",
    "            if (rowq in rownum and rownum[rowq]>0) or (colq in colnum and colnum[colq]>0) or (colq - rowq in diagnum and diagnum[colq-rowq]>0) or (colq + rowq in diag1num and diag1num[colq+rowq]>0):\n",
    "                # 此时当前已经被照亮\n",
    "                res.append(1)\n",
    "            else:\n",
    "                res.append(0)\n",
    "            for row in range(rowq-1,rowq+2):\n",
    "                for col in range(colq-1,colq+2):\n",
    "                    if 0<=row<n and 0<=col<n and (row,col) in lamps_light:\n",
    "                        lamps_light.remove((row,col))\n",
    "                        rownum[row] -= 1\n",
    "                        colnum[col] -= 1\n",
    "                        diagnum[col-row] -= 1\n",
    "                        diag1num[col+row] -= 1\n",
    "        return res\n",
    "      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gridIllumination(self, n: int, lamps: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        rows = {}\n",
    "        cols = {}\n",
    "        d1 = {}\n",
    "        d2 = {}\n",
    "\n",
    "        lamps = set((r,c) for r,c in lamps)\n",
    "\n",
    "        for lamp in lamps:\n",
    "            r, c = lamp\n",
    "            rows.setdefault(r, int()); rows[r] += 1\n",
    "            cols.setdefault(c, int()); cols[c] += 1\n",
    "            d1.setdefault(r+c, int()); d1[r+c] += 1\n",
    "            d2.setdefault(r-c, int()); d2[r-c] += 1\n",
    "\n",
    "        # print(rows)\n",
    "        # print(cols)\n",
    "        # print(d1)\n",
    "        # print(d2)\n",
    "\n",
    "        def close(lamp):\n",
    "            # print(lamp)\n",
    "            lamps.remove(lamp)\n",
    "            r, c = lamp\n",
    "            if r in rows:\n",
    "                rows[r] -= 1\n",
    "                if not rows[r]:\n",
    "                    del rows[r]\n",
    "\n",
    "            if c in cols:\n",
    "                cols[c] -= 1\n",
    "                if not cols[c]:\n",
    "                    del cols[c]\n",
    "\n",
    "            if r+c in d1:\n",
    "                d1[r+c] -= 1\n",
    "                if not d1[r+c]:\n",
    "                    del d1[r+c]\n",
    "\n",
    "            if r-c in d2:\n",
    "                d2[r-c] -= 1\n",
    "                if not d2[r-c]:\n",
    "                    del d2[r-c]\n",
    "\n",
    "        def blockq(r, c):\n",
    "            if r in rows or c in cols or r+c in d1 or r-c in d2:\n",
    "                for sr in [-1,0,1]:\n",
    "                    for sc in [-1,0,1]:\n",
    "                        nr = r+sr\n",
    "                        nc = c+sc\n",
    "                        if 0<=nr<n and 0<=nc<n:\n",
    "                            lamp = (nr,nc)\n",
    "                            if lamp in lamps:\n",
    "                                close(lamp)\n",
    "                return 1\n",
    "            return 0\n",
    "\n",
    "        res = []\n",
    "\n",
    "        for query in queries:\n",
    "            r, c = query\n",
    "            res.append(blockq(r, c))\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gridIllumination(self, n: int, lamps: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        rows = {}\n",
    "        cols = {}\n",
    "        d1 = {}\n",
    "        d2 = {}\n",
    "\n",
    "        lamps = set((r,c) for r,c in lamps)\n",
    "\n",
    "        for lamp in lamps:\n",
    "            r, c = lamp\n",
    "            rows.setdefault(r, int()); rows[r] += 1\n",
    "            cols.setdefault(c, int()); cols[c] += 1\n",
    "            d1.setdefault(r+c, int()); d1[r+c] += 1\n",
    "            d2.setdefault(r-c, int()); d2[r-c] += 1\n",
    "\n",
    "        # print(rows)\n",
    "        # print(cols)\n",
    "        # print(d1)\n",
    "        # print(d2)\n",
    "\n",
    "        def close(lamp):\n",
    "            # print(lamp)\n",
    "            lamps.remove(lamp)\n",
    "            r, c = lamp\n",
    "            if r in rows:\n",
    "                rows[r] -= 1\n",
    "                if not rows[r]:\n",
    "                    del rows[r]\n",
    "\n",
    "            if c in cols:\n",
    "                cols[c] -= 1\n",
    "                if not cols[c]:\n",
    "                    del cols[c]\n",
    "\n",
    "            if r+c in d1:\n",
    "                d1[r+c] -= 1\n",
    "                if not d1[r+c]:\n",
    "                    del d1[r+c]\n",
    "\n",
    "            if r-c in d2:\n",
    "                d2[r-c] -= 1\n",
    "                if not d2[r-c]:\n",
    "                    del d2[r-c]\n",
    "\n",
    "        def blockq(r, c):\n",
    "            if r in rows or c in cols or r+c in d1 or r-c in d2:\n",
    "                for sr in [-1,0,1]:\n",
    "                    for sc in [-1,0,1]:\n",
    "                        nr = r+sr\n",
    "                        nc = c+sc\n",
    "                        if 0<=nr<n and 0<=nc<n:\n",
    "                            lamp = (nr,nc)\n",
    "                            if lamp in lamps:\n",
    "                                close(lamp)\n",
    "                return 1\n",
    "            return 0\n",
    "\n",
    "        res = []\n",
    "\n",
    "        for query in queries:\n",
    "            r, c = query\n",
    "            res.append(blockq(r, c))\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gridIllumination(self, n: int, lamps: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        rows = Counter()\n",
    "        cols = Counter()\n",
    "        sums = Counter()\n",
    "        diffs = Counter()\n",
    "        lamps_set = set()\n",
    "        ans = [0] * len(queries)\n",
    "        for x, y in lamps:\n",
    "            if (x, y) in lamps_set:\n",
    "                continue\n",
    "            rows[x] += 1\n",
    "            cols[y] += 1\n",
    "            sums[x+y] += 1\n",
    "            diffs[x-y] += 1\n",
    "            lamps_set.add((x, y))\n",
    "\n",
    "        for i, (x, y) in enumerate(queries):\n",
    "            if rows[x] or cols[y] or sums[x+y] or diffs[x-y]:\n",
    "                ans[i] = 1\n",
    "            for a, b in product((x+1, x, x-1), (y+1, y, y-1)):\n",
    "                if (a, b) in lamps_set:\n",
    "                    lamps_set.remove((a, b))\n",
    "                    rows[a] -= 1\n",
    "                    cols[b] -= 1\n",
    "                    sums[a+b] -= 1\n",
    "                    diffs[a-b] -= 1\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gridIllumination(self, n: int, lamps: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        res = []\n",
    "        lamp = set()\n",
    "        row, col, posDiag, negDiag = Counter(), Counter(), Counter(), Counter()\n",
    "\n",
    "        for r, c in lamps:\n",
    "            if (r, c) in lamp:\n",
    "                continue\n",
    "            lamp.add((r, c))\n",
    "            row[r] += 1\n",
    "            col[c] += 1\n",
    "            posDiag[r - c] += 1\n",
    "            negDiag[r + c] += 1\n",
    "\n",
    "        \n",
    "        \n",
    "        for r, c in queries:\n",
    "            if row[r] or col[c] or posDiag[r - c] or negDiag[r + c]:\n",
    "                res.append(1)\n",
    "            else:\n",
    "                res.append(0)\n",
    "            # turn off light and adjacents\n",
    "            for x in range(r - 1, r + 2):\n",
    "                for y in range(c - 1, c + 2):\n",
    "                    if x in range(n) and y in range(n) and (x, y) in lamp:\n",
    "                        lamp.remove((x, y))\n",
    "                        row[x] -= 1\n",
    "                        col[y] -= 1\n",
    "                        posDiag[x - y] -= 1\n",
    "                        negDiag[x + y] -= 1\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gridIllumination(self, n: int, lamps: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        lamps_light = set()\n",
    "        colnum = dict() # 保存每一列被照亮的个数\n",
    "        rownum = dict() # 保存每一列被照亮的个数\n",
    "        diagnum = dict() # 保存每一左45列被照亮的个数  y-x\n",
    "        diag1num = dict() # 保存每一右45列被照亮的个数 x+y\n",
    "        res = []\n",
    "        for row,col in lamps:\n",
    "            lamps_light.add(str(row)+\" \"+str(col))\n",
    "        \n",
    "        for light in lamps_light:\n",
    "            rowc,colc = map(int,light.split())\n",
    "            rownum[rowc] = (rownum[rowc] + 1 if rowc in rownum else 1)\n",
    "            colnum[colc] = (colnum[colc] + 1 if colc in colnum else 1)\n",
    "            diagnum[colc - rowc] = (diagnum[colc - rowc] + 1 if colc - rowc in diagnum else 1)\n",
    "            diag1num[colc + rowc] = (diag1num[colc + rowc] + 1 if colc + rowc in diag1num else 1)\n",
    "\n",
    "        for rowq,colq in queries:\n",
    "            if (rowq in rownum and rownum[rowq]>0) or (colq in colnum and colnum[colq]>0) or (colq - rowq in diagnum and diagnum[colq-rowq]>0) or (colq + rowq in diag1num and diag1num[colq+rowq]>0):\n",
    "                # 此时当前已经被照亮\n",
    "                res.append(1)\n",
    "            else:\n",
    "                res.append(0)\n",
    "            for row in range(rowq-1,rowq+2):\n",
    "                for col in range(colq-1,colq+2):\n",
    "                    if 0<=row<n and 0<=col<n:\n",
    "                        str_tmp = str(row)+\" \"+str(col)\n",
    "                        if str_tmp in lamps_light:\n",
    "                            lamps_light.remove(str_tmp)\n",
    "                            rownum[row] -= 1\n",
    "                            colnum[col] -= 1\n",
    "                            diagnum[col-row] -= 1\n",
    "                            diag1num[col+row] -= 1\n",
    "        return res\n",
    "      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import Counter\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def gridIllumination(\n",
    "        self, n: int, lamps: List[List[int]], queries: List[List[int]]\n",
    "    ) -> List[int]:\n",
    "        points = set()\n",
    "        row, col, diagonal, antiDiagonal = Counter(), Counter(), Counter(), Counter()\n",
    "        for r, c in lamps:\n",
    "            if (r, c) in points:\n",
    "                continue\n",
    "            points.add((r, c))\n",
    "            row[r] += 1\n",
    "            col[c] += 1\n",
    "            diagonal[r - c] += 1\n",
    "            antiDiagonal[r + c] += 1\n",
    "\n",
    "        ans = [0] * len(queries)\n",
    "        for i, (r, c) in enumerate(queries):\n",
    "            if (\n",
    "                row[r] > 0\n",
    "                or col[c] > 0\n",
    "                or diagonal[r - c] > 0\n",
    "                or antiDiagonal[r + c] > 0\n",
    "            ):\n",
    "                ans[i] = 1\n",
    "\n",
    "            for x in range(r - 1, r + 2):\n",
    "                for y in range(c - 1, c + 2):\n",
    "                    if x < 0 or x >= n or y < 0 or y >= n or (x, y) not in points:\n",
    "                        continue\n",
    "                    points.remove((x, y))\n",
    "                    row[x] -= 1\n",
    "                    col[y] -= 1\n",
    "                    diagonal[x - y] -= 1\n",
    "                    antiDiagonal[x + y] -= 1\n",
    "        return ans\n",
    "\n",
    "\n",
    "# 每一个灯(坐标)，有五个属性:\n",
    "# 行 (横坐标 x )\n",
    "# 列 (纵坐标 y )\n",
    "# 撇 (直线 y=x+t ⟹\\Longrightarrow⟹ 记录 x-y )\n",
    "# 捺 (直线 x+y=t ⟹\\Longrightarrow⟹ 记录 x+y )\n",
    "# 表示坐标本身的二元组 (坐标 (x,y) )\n",
    "# 前四者之一为真，即亮灯\n",
    "# 然后用哈希表存一下，这五组特性，实时维护开关灯，就OK啦\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def gridIllumination(\n",
    "#         self, n: int, lamps: List[List[int]], queries: List[List[int]]\n",
    "#     ) -> List[int]:\n",
    "#         points = set()\n",
    "#         row, col, diagonal, antiDiagonal = Counter(), Counter(), Counter(), Counter()\n",
    "#         for r, c in lamps:\n",
    "#             if (r, c) in points:\n",
    "#                 continue\n",
    "\n",
    "#             points.add((r, c))\n",
    "#             row[r] += 1\n",
    "#             col[c] += 1\n",
    "#             diagonal[r - c] += 1\n",
    "#             antiDiagonal[r + c] += 1\n",
    "\n",
    "#         ans = [0] * len(queries)\n",
    "#         for i, (r, c) in enumerate(queries):\n",
    "#             if row[r] or col[c] or diagonal[r - c] or antiDiagonal[r + c]:\n",
    "#                 ans[i] = 1\n",
    "\n",
    "#             for x in range(r - 1, r + 2):\n",
    "#                 for y in range(c - 1, c + 2):\n",
    "#                     # for i1, j1 in dirs:\n",
    "#                     #     r, c = i + i1, j + j1\n",
    "#                     if x < 0 or y < 0 or x >= n or y >= n or (x, y) not in points:\n",
    "#                         continue\n",
    "\n",
    "#                     points.remove((x, y))\n",
    "#                     row[x] -= 1\n",
    "#                     col[y] -= 1\n",
    "#                     diagonal[x - y] -= 1\n",
    "#                     antiDiagonal[x + y] -= 1\n",
    "#         return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gridIllumination(self, n: int, lamps: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        points = set()\n",
    "        row, col, diagonal, antiDiagonal = Counter(), Counter(), Counter(), Counter()\n",
    "        for r, c in lamps:\n",
    "            if (r, c) in points:\n",
    "                continue\n",
    "            points.add((r, c))\n",
    "            row[r] += 1\n",
    "            col[c] += 1\n",
    "            diagonal[r - c] += 1\n",
    "            antiDiagonal[r + c] += 1\n",
    "\n",
    "        ans = [0] * len(queries)\n",
    "        for i, (r, c) in enumerate(queries):\n",
    "            if row[r] or col[c] or diagonal[r - c] or antiDiagonal[r + c]:\n",
    "                ans[i] = 1\n",
    "            for x in range(r - 1, r + 2):\n",
    "                for y in range(c - 1, c + 2):\n",
    "                    if x < 0 or y < 0 or x >= n or y >= n or (x, y) not in points:\n",
    "                        continue\n",
    "                    points.remove((x, y))\n",
    "                    row[x] -= 1\n",
    "                    col[y] -= 1\n",
    "                    diagonal[x - y] -= 1\n",
    "                    antiDiagonal[x + y] -= 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gridIllumination(self, n: int, lamps: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        points = set()\n",
    "        row, col, diagonal, antiDiagonal = Counter(), Counter(), Counter(), Counter()\n",
    "        for r, c in lamps:\n",
    "            if (r, c) in points:\n",
    "                continue\n",
    "            points.add((r, c))\n",
    "            row[r] += 1\n",
    "            col[c] += 1\n",
    "            diagonal[r - c] += 1\n",
    "            antiDiagonal[r + c] += 1\n",
    "        ans = [0] * len(queries)\n",
    "        for i, (r, c) in enumerate(queries):\n",
    "            if row[r] or col[c] or diagonal[r - c] or antiDiagonal[r + c]:\n",
    "                ans[i] = 1\n",
    "            for x in range(r - 1, r + 2):\n",
    "                for y in range(c - 1, c + 2):\n",
    "                    if x < 0 or y < 0 or x >= n or y >= n or (x, y) not in points:\n",
    "                        continue\n",
    "                    points.remove((x, y))\n",
    "                    row[x] -= 1\n",
    "                    col[y] -= 1\n",
    "                    diagonal[x - y] -= 1\n",
    "                    antiDiagonal[x + y] -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gridIllumination(self, n: int, lamps: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        points = set()\n",
    "        row, col, diagonal, antiDiagonal = Counter(), Counter(), Counter(), Counter()\n",
    "        for r, c in lamps:\n",
    "            if (r, c) in points:\n",
    "                continue\n",
    "            points.add((r, c))\n",
    "            row[r] += 1\n",
    "            col[c] += 1\n",
    "            diagonal[r - c] += 1\n",
    "            antiDiagonal[r + c] += 1\n",
    "        ans = [0] * len(queries)\n",
    "        for i, (r, c) in enumerate(queries):\n",
    "            if row[r] or col[c] or diagonal[r - c] or antiDiagonal[r + c]:\n",
    "                ans[i] = 1\n",
    "            for x in range(r - 1, r + 2):\n",
    "                for y in range(c - 1, c + 2):\n",
    "                    if x < 0 or y < 0 or x >= n or y >= n or (x, y) not in points:\n",
    "                        continue\n",
    "                    points.remove((x, y))\n",
    "                    row[x] -= 1\n",
    "                    col[y] -= 1\n",
    "                    diagonal[x - y] -= 1\n",
    "                    antiDiagonal[x + y] -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gridIllumination(self, n: int, lamps: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        points = set()\n",
    "        row, col, diagonal, antiDiagonal = Counter(), Counter(), Counter(), Counter()\n",
    "        for r, c in lamps:\n",
    "            if (r, c) in points:\n",
    "                continue\n",
    "            points.add((r, c))\n",
    "            row[r] += 1\n",
    "            col[c] += 1\n",
    "            diagonal[r - c] += 1\n",
    "            antiDiagonal[r + c] += 1\n",
    "\n",
    "        ans = [0] * len(queries)\n",
    "        for i, (r, c) in enumerate(queries):\n",
    "            if row[r] or col[c] or diagonal[r - c] or antiDiagonal[r + c]:\n",
    "                ans[i] = 1\n",
    "            for x in range(r - 1, r + 2):\n",
    "                for y in range(c - 1, c + 2):\n",
    "                    if x < 0 or y < 0 or x >= n or y >= n or (x, y) not in points:\n",
    "                        continue\n",
    "                    points.remove((x, y))\n",
    "                    row[x] -= 1\n",
    "                    col[y] -= 1\n",
    "                    diagonal[x - y] -= 1\n",
    "                    antiDiagonal[x + y] -= 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def gridIllumination(self, n: int, lamps: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        rows, cols, diag1, diag2, lamps_on = {}, {}, {}, {}, set()\n",
    "        \n",
    "        # 用于查询周围8个方向的偏移量\n",
    "        directions = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1), (0, 0)]\n",
    "        \n",
    "        # 初始化字典和灯的集合\n",
    "        for x, y in lamps:\n",
    "            if (x, y) not in lamps_on:  # 防止重复计数\n",
    "                rows[x] = rows.get(x, 0) + 1\n",
    "                cols[y] = cols.get(y, 0) + 1\n",
    "                diag1[x-y] = diag1.get(x-y, 0) + 1\n",
    "                diag2[x+y] = diag2.get(x+y, 0) + 1\n",
    "                lamps_on.add((x, y))\n",
    "        \n",
    "        res = []\n",
    "        for x, y in queries:\n",
    "            # 检查该位置是否被照亮\n",
    "            if rows.get(x, 0) > 0 or cols.get(y, 0) > 0 or diag1.get(x-y, 0) > 0 or diag2.get(x+y, 0) > 0:\n",
    "                res.append(1)\n",
    "            else:\n",
    "                res.append(0)\n",
    "            \n",
    "            # 关闭附近的灯\n",
    "            for dx, dy in directions:\n",
    "                nx, ny = x + dx, y + dy\n",
    "                if (nx, ny) in lamps_on:\n",
    "                    lamps_on.remove((nx, ny))\n",
    "                    rows[nx] = rows.get(nx, 0) - 1\n",
    "                    cols[ny] = cols.get(ny, 0) - 1\n",
    "                    diag1[nx-ny] = diag1.get(nx-ny, 0) - 1\n",
    "                    diag2[nx+ny] = diag2.get(nx+ny, 0) - 1\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gridIllumination(self, n: int, lamps: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        points = set()\n",
    "        row,col,diagonal,antidiagonal = Counter(),Counter(),Counter(),Counter()\n",
    "        # 预处理\n",
    "        for r,c in lamps:\n",
    "            if (r,c) in points:\n",
    "                continue\n",
    "            points.add((r,c))\n",
    "            row[r] += 1\n",
    "            col[c] += 1\n",
    "            diagonal[r-c] += 1\n",
    "            antidiagonal[r+c] += 1\n",
    "        \n",
    "        ans = [0]*len(queries)\n",
    "        for i,(r,c) in enumerate(queries):\n",
    "            if row[r] or col[c] or diagonal[r-c] or antidiagonal[r+c]:\n",
    "                ans[i] = 1\n",
    "            for x in range(r-1,r+2):\n",
    "                for y in range(c-1,c+2):\n",
    "                    if x < 0 or y < 0 or x >= n or y >= n or (x,y) not in points:\n",
    "                        continue\n",
    "                    points.remove((x,y))\n",
    "                    row[x] -= 1\n",
    "                    col[y] -= 1\n",
    "                    diagonal[x-y] -= 1\n",
    "                    antidiagonal[x+y] -= 1\n",
    "        return ans\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gridIllumination(self, n: int, lamps: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        # 看每一次查询它所在的行，列，正斜线，反斜线是否被照亮\n",
    "        # 预处理\n",
    "        seen = set()\n",
    "        row,col,slash,antislash = Counter(),Counter(),Counter(),Counter()\n",
    "        for r,c in lamps:\n",
    "            if (r,c) in seen:\n",
    "                continue\n",
    "            seen.add((r,c))\n",
    "            row[r] += 1\n",
    "            col[c] += 1\n",
    "            slash[r-c] += 1\n",
    "            antislash[r+c] += 1\n",
    "        # 查询结果\n",
    "        ans = [0]*len(queries)\n",
    "        for i,(r,c) in enumerate(queries):\n",
    "            if row[r] or col[c] or slash[r-c] or antislash[r+c]:\n",
    "                ans[i] = 1\n",
    "            # 枚举它的临边格子\n",
    "            for x in range(r-1,r+2):\n",
    "                for y in range(c-1,c+2):\n",
    "                    if x < 0 or y < 0 or x >=n or y >= n or (x,y) not in seen:\n",
    "                        continue\n",
    "                    seen.remove((x,y))\n",
    "                    row[x] -= 1\n",
    "                    col[y] -= 1\n",
    "                    slash[x-y] -= 1\n",
    "                    antislash[x+y] -= 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def gridIllumination(self, n: int, lamps: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "#         light = set()\n",
    "#         row = defaultdict(set)\n",
    "#         col = defaultdict(set)\n",
    "#         left = defaultdict(set)\n",
    "#         right = defaultdict(set)\n",
    "\n",
    "#         for x,y in lamps:\n",
    "#             light.add((x,y))\n",
    "#             row[x].add(y)\n",
    "#             col[y].add(x)\n",
    "#             left[x+y].add((x,y))\n",
    "#             right[x-y].add((x,y))\n",
    "#         # print(\"light:\",light)\n",
    "#         # print(\"row:\",row)\n",
    "#         # print(\"col:\",col)\n",
    "#         # print(\"left:\",left)\n",
    "#         # print(\"right:\",right)\n",
    "#         ans = []\n",
    "#         for x,y in queries:\n",
    "#             if x in row or y in col or x+y in left or x-y in right:\n",
    "#                 ans.append(1)\n",
    "#             else:\n",
    "#                 ans.append(0)\n",
    "#             for dx,dy in [(-1,-1),(-1,0),(-1,1),(0,-1),(0,0),(0,1),(1,-1),(1,0),(1,1)]:\n",
    "#                 nx,ny = x+dx,y+dy\n",
    "#                 if 0<=nx<n and 0<=ny<n and (nx,ny) in light:\n",
    "#                     light.remove((nx,ny))\n",
    "#                     #弹出行\n",
    "#                     if nx in row and ny in row[nx]:\n",
    "#                         row[nx].remove(ny)\n",
    "#                         if not row[nx]:\n",
    "#                             row.pop(nx)\n",
    "#                     #弹出列\n",
    "#                     if ny in col and nx in col[ny]:\n",
    "#                         col[ny].remove(nx)\n",
    "#                         if not col[ny]:\n",
    "#                             col.pop(ny)\n",
    "#                     #弹出左斜\n",
    "#                     if nx+ny in left and (nx,ny) in left[nx+ny]:\n",
    "#                         left[nx+ny].remove((nx,ny))\n",
    "#                         if not left[nx+ny]:\n",
    "#                             left.pop(nx+ny)\n",
    "#                     #弹出右斜\n",
    "#                     if nx-ny in right and (nx,ny) in right[nx-ny]:\n",
    "#                         right[nx-ny].remove((nx,ny))\n",
    "#                         if not right[nx-ny]:\n",
    "#                             right.pop(nx-ny)\n",
    "#         # print(\"light:\",light)\n",
    "#         # print(\"row:\",row)\n",
    "#         # print(\"col:\",col)\n",
    "#         # print(\"left:\",left)\n",
    "#         # print(\"right:\",right)\n",
    "#         return ans\n",
    "class Solution:\n",
    "    def gridIllumination(self, n: int, lamps: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        points = set()\n",
    "        row, col, diagonal, antiDiagonal = Counter(), Counter(), Counter(), Counter()\n",
    "        for r, c in lamps:\n",
    "            if (r, c) in points:\n",
    "                continue\n",
    "            points.add((r, c))\n",
    "            row[r] += 1\n",
    "            col[c] += 1\n",
    "            diagonal[r - c] += 1\n",
    "            antiDiagonal[r + c] += 1\n",
    "\n",
    "        ans = [0] * len(queries)\n",
    "        for i, (r, c) in enumerate(queries):\n",
    "            if row[r] or col[c] or diagonal[r - c] or antiDiagonal[r + c]:\n",
    "                ans[i] = 1\n",
    "            for x in range(r - 1, r + 2):\n",
    "                for y in range(c - 1, c + 2):\n",
    "                    if x < 0 or y < 0 or x >= n or y >= n or (x, y) not in points:\n",
    "                        continue\n",
    "                    points.remove((x, y))\n",
    "                    row[x] -= 1\n",
    "                    col[y] -= 1\n",
    "                    diagonal[x - y] -= 1\n",
    "                    antiDiagonal[x + y] -= 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gridIllumination(self, n: int, lamps: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        row, col, dia, antidia = Counter(), Counter(), Counter(), Counter()\n",
    "        points = set()\n",
    "        dirs = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 0), (0, 1), (1, -1), (1, 0), (1, 1)]\n",
    "\n",
    "        for x, y in lamps:\n",
    "            if (x, y) in points:\n",
    "                continue\n",
    "            points.add((x, y))\n",
    "            row[x] += 1\n",
    "            col[y] += 1\n",
    "            dia[x - y] += 1\n",
    "            antidia[x + y] += 1\n",
    "        \n",
    "        m = len(queries)\n",
    "        ans = [0] * m\n",
    "        for i, (x, y) in enumerate(queries):\n",
    "            if row[x] or col[y] or dia[x-y] or antidia[x+y]:\n",
    "                ans[i] = 1\n",
    "            for dx, dy in dirs:\n",
    "                nx, ny = x+dx, y+dy\n",
    "                if nx < 0 or nx > n-1 or ny < 0 or ny > n-1 or not(nx, ny) in points:\n",
    "                    continue\n",
    "                points.remove((nx, ny))\n",
    "                row[nx] -= 1\n",
    "                col[ny] -= 1\n",
    "                dia[nx - ny] -= 1\n",
    "                antidia[nx + ny] -= 1\n",
    "        \n",
    "        return ans\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gridIllumination(self, n: int, lamps: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        rows = Counter()\n",
    "        cols = Counter()\n",
    "        d1 = Counter()\n",
    "        d2 = Counter()\n",
    "\n",
    "        lamps = set((r,c) for r,c in lamps)\n",
    "\n",
    "        for lamp in lamps:\n",
    "            r, c = lamp\n",
    "            rows[r] += 1\n",
    "            cols[c] += 1\n",
    "            d1[r+c] += 1\n",
    "            d2[r-c] += 1\n",
    "\n",
    "        # print(rows)\n",
    "        # print(cols)\n",
    "        # print(d1)\n",
    "        # print(d2)\n",
    "\n",
    "        def close(lamp):\n",
    "            # print(lamp)\n",
    "            lamps.remove(lamp)\n",
    "            r, c = lamp\n",
    "            if r in rows:\n",
    "                rows[r] -= 1\n",
    "                if not rows[r]:\n",
    "                    del rows[r]\n",
    "\n",
    "            if c in cols:\n",
    "                cols[c] -= 1\n",
    "                if not cols[c]:\n",
    "                    del cols[c]\n",
    "\n",
    "            if r+c in d1:\n",
    "                d1[r+c] -= 1\n",
    "                if not d1[r+c]:\n",
    "                    del d1[r+c]\n",
    "\n",
    "            if r-c in d2:\n",
    "                d2[r-c] -= 1\n",
    "                if not d2[r-c]:\n",
    "                    del d2[r-c]\n",
    "\n",
    "        def blockq(r, c):\n",
    "            if r in rows or c in cols or r+c in d1 or r-c in d2:\n",
    "                for sr in [-1,0,1]:\n",
    "                    for sc in [-1,0,1]:\n",
    "                        nr = r+sr\n",
    "                        nc = c+sc\n",
    "                        if 0<=nr<n and 0<=nc<n:\n",
    "                            lamp = (nr,nc)\n",
    "                            if lamp in lamps:\n",
    "                                close(lamp)\n",
    "                return 1\n",
    "            return 0\n",
    "\n",
    "        res = []\n",
    "\n",
    "        for query in queries:\n",
    "            r, c = query\n",
    "            res.append(blockq(r, c))\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gridIllumination(self, n: int, lamps: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        light = set(map(tuple, lamps))\n",
    "        row = defaultdict(int)\n",
    "        col = defaultdict(int)\n",
    "        xie = defaultdict(int)\n",
    "        xie2 = defaultdict(int)\n",
    "        res = []\n",
    "        for x, y in light:\n",
    "            row[x] += 1\n",
    "            col[y] += 1\n",
    "            xie[x-y] += 1\n",
    "            xie2[x+y] += 1\n",
    "        for qx, qy in queries:\n",
    "            if row[qx] or col[qy] or xie[qx-qy] or xie2[qx+qy]:\n",
    "                res.append(1)\n",
    "            else:\n",
    "                res.append(0)\n",
    "            for tx in (-1, 0, 1):\n",
    "                for ty in (-1, 0, 1):\n",
    "                    if (qx+tx, qy+ty) in light:\n",
    "                        light.remove((qx+tx, qy+ty))\n",
    "                        row[qx+tx] -= 1\n",
    "                        col[qy+ty] -= 1\n",
    "                        xie[qx+tx-qy-ty] -= 1\n",
    "                        xie2[qx+tx+qy+ty] -= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gridIllumination(self, n: int, lamps: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        ans = [0] * len(queries)\n",
    "        row_cnts, col_cnts, lr_cnts, rl_cnts = defaultdict(int), defaultdict(int), defaultdict(int), defaultdict(int)\n",
    "        points = set()\n",
    "        for x,y in lamps:\n",
    "            if (x,y) not in points:\n",
    "                points.add((x,y))\n",
    "                row_cnts[x] +=1\n",
    "                col_cnts[y] +=1\n",
    "                lr_cnts[x+y] +=1\n",
    "                rl_cnts[x-y] +=1\n",
    "        for i in range(len(queries)):\n",
    "            x,y = queries[i]\n",
    "            if row_cnts[x] or col_cnts[y] or lr_cnts[x+y] or rl_cnts[x-y]:\n",
    "                ans[i] = 1\n",
    "                for nx,ny in [(x, y), (x + 1, y + 1), (x + 1, y), (x + 1, y - 1), (x, y + 1), (x, y - 1), (x - 1, y - 1),(x - 1, y), (x - 1, y + 1)]:\n",
    "                    if (nx,ny) in points:\n",
    "                        points.remove((nx,ny))\n",
    "                        row_cnts[nx] -= 1\n",
    "                        col_cnts[ny] -= 1\n",
    "                        lr_cnts[nx + ny] -= 1\n",
    "                        rl_cnts[nx - ny] -= 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gridIllumination(self, n: int, lamps: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        row, col, dig, antidig = defaultdict(int), defaultdict(int), defaultdict(int), defaultdict(int)\n",
    "        points = set()\n",
    "        for x, y in lamps:\n",
    "            if not (x, y) in points:\n",
    "                row[x] += 1\n",
    "                col[y] += 1\n",
    "                dig[x - y] += 1\n",
    "                antidig[x + y] += 1\n",
    "            points.add((x, y))\n",
    "        \n",
    "        ans = [0] * len(queries)\n",
    "\n",
    "        dirs = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 0), (0, 1), (1, -1), (1, 0), (1, 1)]\n",
    "        \n",
    "        for i, (x, y) in enumerate(queries):\n",
    "            if row[x] or col[y] or dig[x - y] or antidig[x+y]:\n",
    "                ans[i] = 1\n",
    "            for dx, dy in dirs:\n",
    "                nx, ny = x + dx, y+dy\n",
    "                if 0 <= nx <= n-1 and 0<=ny<=n-1 and (nx, ny) in points:\n",
    "                    points.remove((nx, ny))\n",
    "                    row[nx] -= 1\n",
    "                    col[ny] -= 1\n",
    "                    dig[nx - ny] -= 1\n",
    "                    antidig[nx + ny] -= 1\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gridIllumination(self, n: int, lamps: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        a = set()\n",
    "        cols = defaultdict(int)\n",
    "        rows = defaultdict(int)\n",
    "        lines1 = defaultdict(int)\n",
    "        lines2 = defaultdict(int)\n",
    "        for r,c in lamps:\n",
    "            if (r,c) in a:\n",
    "                continue\n",
    "            a.add((r,c))\n",
    "            cols[c] += 1\n",
    "            rows[r] += 1\n",
    "            lines1[r - c] += 1\n",
    "            lines2[r + c] += 1\n",
    "        ans = []\n",
    "        for r,c in queries:\n",
    "            if (r,c) in a or rows[r] or cols[c] or lines2[r + c] or lines1[r - c]:\n",
    "                ans.append(1)\n",
    "                if (r,c) in a:\n",
    "                    a.remove((r,c))\n",
    "                    rows[r] -= 1\n",
    "                    cols[c] -= 1\n",
    "                    lines2[r + c] -= 1\n",
    "                    lines1[r - c] -= 1\n",
    "            else:\n",
    "                ans.append(0)\n",
    "\n",
    "            for i in (-1,0,1):\n",
    "                for j in (-1,0,1):\n",
    "                    if i == j == 0:\n",
    "                        continue\n",
    "                    nr,nc = r + i,c + j\n",
    "                    if 0 <= nr < n and 0 <= nc < n:\n",
    "                        if (nr,nc) not in a:\n",
    "                            continue\n",
    "                        a.remove((nr,nc))\n",
    "                        rows[nr] -= 1\n",
    "                        cols[nc] -= 1\n",
    "                        lines2[nr + nc] -= 1\n",
    "                        lines1[nr - nc] -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gridIllumination(self, n: int, lamps: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        row,col,lr,rl,points=defaultdict(int),defaultdict(int),defaultdict(int),defaultdict(int),set()\n",
    "        for r,c in lamps:\n",
    "            if (r,c) not in points:\n",
    "                points.add((r,c))\n",
    "                row[r]+=1\n",
    "                col[c]+=1\n",
    "                lr[r+c]+=1\n",
    "                rl[r-c]+=1\n",
    "        ans=[0]*len(queries)\n",
    "        for i in range(len(queries)):\n",
    "            r,c=queries[i]\n",
    "            if row[r] or col[c] or lr[r+c] or rl[r-c]:\n",
    "                ans[i]=1\n",
    "                for dx,dy in (0, 1), (1, 0), (0, -1), (-1, 0), (0, 0), (1, 1), (-1, 1), (1, -1), (-1, -1):\n",
    "                    nx=r+dx\n",
    "                    ny=c+dy\n",
    "                    if (nx,ny) in points:\n",
    "                        points.remove((nx,ny))\n",
    "                        row[nx]-=1\n",
    "                        col[ny]-=1\n",
    "                        lr[nx+ny]-=1\n",
    "                        rl[nx-ny]-=1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gridIllumination(self, n: int, lamps: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        row_cnts, col_cnts, lr_cnts, rl_cnts, points = defaultdict(int), defaultdict(int), defaultdict(int), defaultdict(int), set()\n",
    "        for r, c in lamps:\n",
    "            if (r, c) not in points:\n",
    "                points.add((r, c))\n",
    "                row_cnts[r] += 1\n",
    "                col_cnts[c] += 1\n",
    "                # r * (-1) + b = c\n",
    "                lr_cnts[r + c] += 1 #右对角线\n",
    "                # r + b = c\n",
    "                rl_cnts[r - c] += 1 #左对角线\n",
    "        ans = [0] * len(queries)\n",
    "        for i in range(len(queries)):\n",
    "            r, c = queries[i]\n",
    "            if row_cnts[r] or col_cnts[c] or lr_cnts[r + c] or rl_cnts[r - c]:\n",
    "                ans[i] = 1\n",
    "                for dx, dy in (0, 1), (1, 0), (0, -1), (-1, 0), (0, 0), (1, 1), (-1, 1), (1, -1), (-1, -1):\n",
    "                    if ((nx := r + dx),(ny := c + dy)) in points:\n",
    "                        points.remove((nx, ny))\n",
    "                        row_cnts[nx] -= 1\n",
    "                        col_cnts[ny] -= 1\n",
    "                        lr_cnts[nx + ny] -= 1\n",
    "                        rl_cnts[nx - ny] -= 1\n",
    "        return ans\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gridIllumination(self, n: int, lamps: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        row_cnt, col_cnt, lr_cnt, rl_cnt, points = defaultdict(int), defaultdict(int), defaultdict(int), defaultdict(int), set()\n",
    "        directions = [(-1, 0), (1, 0), (0, -1), (0, 1), (1, 1), (-1, -1), (-1, 1), (1, -1), (0, 0)]\n",
    "        for r, c in lamps:\n",
    "            if (r, c) not in points:\n",
    "                points.add((r, c))\n",
    "                row_cnt[r] += 1\n",
    "                col_cnt[c] += 1\n",
    "                lr_cnt[r+c] += 1\n",
    "                rl_cnt[r-c] += 1\n",
    "        ans = [0] * len(queries)\n",
    "        for i in range(len(queries)):\n",
    "            r, c = queries[i]\n",
    "            if row_cnt[r] or col_cnt[c] or lr_cnt[r+c] or rl_cnt[r-c]:\n",
    "                # 记录这个地方是否被某个灯照到了\n",
    "                ans[i] = 1\n",
    "                for dx, dy in directions: # 把周围的灯关掉\n",
    "                    nx = r + dx\n",
    "                    ny = c + dy\n",
    "                    if (nx, ny) in points:\n",
    "                        points.remove((nx, ny))\n",
    "                        # 关灯之后，这个灯能照到的地方-1\n",
    "                        row_cnt[nx] -= 1\n",
    "                        col_cnt[ny] -= 1\n",
    "                        lr_cnt[nx + ny] -= 1\n",
    "                        rl_cnt[nx - ny] -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gridIllumination(self, n: int, lamps: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        \"\"\"\n",
    "        题目要求：本质就是 n*n的二维表中，给定灯坐标lamps[i]=[row, col]表示打开该位置及其同行同列同对角线上的所有灯，查询位置坐标queries[j]=[row, col]对应\n",
    "                位置的等是否被点亮(亮1暗0)，查询该位置后，该位置为中心的九宫格灯全部熄灭，最后返回每个查询坐标的亮暗情况\n",
    "        :param n: 给定的二维表的边长\n",
    "        :param lamps: 给定的灯坐标数组\n",
    "        :param queries: 给定的查询位置坐标数组\n",
    "        :return: 返回查询位置的亮暗情况\n",
    "        \"\"\"\n",
    "        # 解题思路：将有亮灯的行、列和两个方向的对角线进行标记数量即可(显然哈希表(字典)咯，其实python也能用Counter类)\n",
    "        # 如何判定是否被照亮：\n",
    "        # 同行，同列容易判定，建立以行、列索引为key的哈希表即可\n",
    "        # 左上右下的对角线，x-y是个固定值，可以建立以这个差作为key的哈希表\n",
    "        # 右上左下的对角线，x+y是个固定值，可以建立以这个和作为key的哈希表\n",
    "        # 大致流程：先遍历lamps，将当前遍历到的灯所在的行，列和正/反对角线拥有灯的数目分别加一(切记去重，不要重复点亮，超时！！！)\n",
    "        # 然后遍历queries，判断当前查询点所在的行，列和正/反对角线是否有灯，如果有则为1\n",
    "        # 最后进行熄灯操作，查找该位置为中心的九宫格是否亮灯，如果有将该位置所在的行，列和正/反对角线的灯数目分别减一，并且将灯从网格中去掉\n",
    "        # 初始化四种哈希表存储亮灯数量(用Counter也行，本质还是字典)\n",
    "        row_dic = defaultdict(int)\n",
    "        col_dic = defaultdict(int)\n",
    "        diag_dic = defaultdict(int)\n",
    "        anti_diag_dic = defaultdict(int)\n",
    "        lamp_set = set()  # 标记是否点亮集合\n",
    "        for r, c in lamps:  # 遍历lamps初始化哈希表\n",
    "            if (r, c) in lamp_set:  # 已经亮了，直接跳过(不能省略，否则错误，会重复点亮加1，大坑！！)\n",
    "                continue\n",
    "            lamp_set.add((r, c))  # 标记点亮了\n",
    "            # 对应四种点亮情况数量加1\n",
    "            row_dic[r] += 1\n",
    "            col_dic[c] += 1\n",
    "            diag_dic[r - c] += 1\n",
    "            anti_diag_dic[r + c] += 1\n",
    "        res = []  # 返回的结果列表\n",
    "        for r, c in queries:  # 遍历queries，计算结果\n",
    "            # 任一种情况有灯则为1\n",
    "            if row_dic[r] or col_dic[c] or diag_dic[r - c] or anti_diag_dic[r + c]:\n",
    "                res.append(1)\n",
    "            else:  # 否则为0\n",
    "                res.append(0)\n",
    "            # 最后熄灯操作，依次遍历九个位置\n",
    "            for nr, nc in (\n",
    "                    (r - 1, c - 1), (r - 1, c), (r - 1, c + 1), (r, c - 1), (r, c), (r, c + 1), (r + 1, c - 1), (r + 1, c),\n",
    "                    (r + 1, c + 1)):\n",
    "                if (nr, nc) in lamp_set:  # 亮的才处理，不亮的不用管，费时\n",
    "                    lamp_set.remove((nr, nc))  # 标记熄灭\n",
    "                    # 熄灯，对应位置四种情况减1\n",
    "                    row_dic[nr] -= 1\n",
    "                    col_dic[nc] -= 1\n",
    "                    diag_dic[nr - nc] -= 1\n",
    "                    anti_diag_dic[nr + nc] -= 1\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gridIllumination(self, n: int, lamps: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        open=set()\n",
    "        row, col, diag, antidiag = defaultdict(int), defaultdict(int), defaultdict(int), defaultdict(int)\n",
    "\n",
    "        for i,j in lamps:\n",
    "            if (i,j) not in open:\n",
    "                open.add((i,j))\n",
    "                row[i]+=1\n",
    "                col[j]+=1\n",
    "                diag[j-i+n-1]+=1\n",
    "                antidiag[i+j]+=1\n",
    "\n",
    "        ans=[]\n",
    "        for i,j in queries:\n",
    "            if row[i] or col[j] or diag[j-i+n-1] or antidiag[i+j]:\n",
    "                ans.append(1)\n",
    "            else:\n",
    "                ans.append(0)\n",
    "                continue\n",
    "\n",
    "            for x,y in [(i,j),(i-1,j),(i-1,j-1),(i-1,j+1),(i+1,j),(i+1,j-1),(i+1,j+1),(i,j+1),(i,j-1)]:\n",
    "                if (x,y) in open:\n",
    "                    open.remove((x,y))\n",
    "                    row[x]-=1\n",
    "                    col[y]-=1\n",
    "                    diag[y-x+n-1]-=1\n",
    "                    antidiag[x+y]-=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gridIllumination(self, n: int, lamps: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        ans=[0]*len(queries)\n",
    "        lamps=set([tuple(i) for i in lamps])\n",
    "        dicc=Counter()\n",
    "        for i in lamps:\n",
    "            dicc[(i[0],-1)]+=1\n",
    "            dicc[(-1,i[1])]+=1\n",
    "            dicc[('+',i[0]+i[1])]+=1\n",
    "            dicc[('-',i[0]-i[1])]+=1\n",
    "        ll=[[-1,-1],[-1,0],[-1,1],[0,-1],[0,0],[0,1],[1,-1],[1,0],[1,1]]\n",
    "\n",
    "        for i in range(len(queries)):\n",
    "            t=queries[i]\n",
    "            if (t[0],-1) in dicc or (-1,t[1]) in dicc or ('+',t[0]+t[1]) in dicc or ('-',t[0]-t[1]) in dicc:ans[i]=1\n",
    "            for ii,jj in ll:\n",
    "                newi,newj=t[0]+ii,t[1]+jj\n",
    "                if 0<=newi<n and 0<=newj<n and (newi,newj) in lamps:\n",
    "\n",
    "                    dicc[(newi,-1)]-=1\n",
    "                    if dicc[(newi,-1)]==0:del dicc[(newi,-1)]\n",
    "\n",
    "                    dicc[(-1,newj)]-=1\n",
    "                    if dicc[(-1,newj)]==0:del dicc[(-1,newj)]\n",
    "\n",
    "                    dicc[('+',newi+newj)]-=1\n",
    "                    if dicc[('+',newi+newj)]==0:del dicc[('+',newi+newj)]\n",
    "\n",
    "                    dicc[('-',newi-newj)]-=1\n",
    "                    if dicc[('-',newi-newj)]==0:del dicc[('-',newi-newj)]\n",
    "\n",
    "                    lamps.remove((newi,newj))\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gridIllumination(self, n: int, l: List[List[int]], q: List[List[int]]) -> List[int]:\n",
    "        a = defaultdict(int)\n",
    "        b = defaultdict(int)\n",
    "        c = defaultdict(int)\n",
    "        d = defaultdict(int)  \n",
    "        s = set()\n",
    "        def check(i, j):\n",
    "            # nonlocal a, b, c, d\n",
    "            if a[i] or b[j] or c[i+j] or d[n-1-j+i]:\n",
    "                return 1 \n",
    "            return 0 \n",
    "        \n",
    "        def put(i, j):\n",
    "            # nonlocal s, a, b, c, d \n",
    "            s.add((i, j)) \n",
    "            a[i] += 1 \n",
    "            b[j] += 1 \n",
    "            c[i+j] += 1 \n",
    "            d[n-1-j+i] += 1 \n",
    "\n",
    "        def cut(i, j):\n",
    "            # nonlocal s, a, b, c, d \n",
    "            for x in range(i-1, i+2):\n",
    "                for y in range(j-1, j+2):\n",
    "                    if (0<=x<n) and (0<=y<n):\n",
    "                        if (x, y) in s:\n",
    "                            s.remove((x, y)) \n",
    "                            a[x] -= 1 \n",
    "                            b[y] -= 1 \n",
    "                            c[x+y] -= 1 \n",
    "                            d[n-1-y+x] -= 1 \n",
    "        t = set([(i, j) for i, j in l]) \n",
    "        for i, j in t:\n",
    "            put(i, j) \n",
    "        ans = []\n",
    "        for i, j in q:\n",
    "            ans.append(check(i, j)) \n",
    "            cut(i, j) \n",
    "            # print(s)\n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gridIllumination(self, n: int, lamps: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        rows, cols = {}, {}\n",
    "        diag1, diag2 = {}, {}\n",
    "        for x, y in lamps:\n",
    "            if x not in rows:\n",
    "                rows[x] = set()\n",
    "            rows[x].add(y)\n",
    "            if y not in cols:\n",
    "                cols[y] = set()\n",
    "            cols[y].add(x)\n",
    "            id1, id2 = x - y, x + y\n",
    "            if id1 not in diag1:\n",
    "                diag1[id1] = set()\n",
    "            diag1[id1].add(x)\n",
    "            if id2 not in diag2:\n",
    "                diag2[id2] = set()\n",
    "            diag2[id2].add(x)\n",
    "\n",
    "        res = []\n",
    "        for x, y in queries:\n",
    "            if (x in rows and len(rows[x]) > 0) or (y in cols and len(cols[y]) > 0) or ((x - y) in diag1 and len(diag1[x - y]) > 0) or ((x + y) in diag2 and len(diag2[x + y]) > 0):\n",
    "                res.append(1)\n",
    "            else:\n",
    "                res.append(0)\n",
    "            for offset1 in [-1, 0, 1]:\n",
    "                for offset2 in [-1, 0, 1]:\n",
    "                    x2, y2 = x + offset1, y + offset2\n",
    "                    if x2 < 0 or x2 >= n or y2 < 0 or y2 >= n:\n",
    "                        continue\n",
    "                    if x2 in rows and y2 in rows[x2]:\n",
    "                        rows[x2].discard(y2)\n",
    "                        cols[y2].discard(x2)\n",
    "                        diag1[x2 - y2].discard(x2)\n",
    "                        diag2[x2 + y2].discard(x2)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gridIllumination(self, n: int, lamps: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        rows = {}\n",
    "        cols = {}\n",
    "        d1 = {}\n",
    "        d2 = {}\n",
    "\n",
    "        lamps = set((r,c) for r,c in lamps)\n",
    "\n",
    "        for lamp in lamps:\n",
    "            r, c = lamp\n",
    "            rows.setdefault(r, set()).add(lamp)\n",
    "            cols.setdefault(c, set()).add(lamp)\n",
    "            d1.setdefault(r+c, set()).add(lamp)\n",
    "            d2.setdefault(r-c, set()).add(lamp)\n",
    "\n",
    "        # print(rows)\n",
    "        # print(cols)\n",
    "        # print(d1)\n",
    "        # print(d2)\n",
    "\n",
    "        def close(lamp):\n",
    "            # print(lamp)\n",
    "            lamps.remove(lamp)\n",
    "            r, c = lamp\n",
    "            if r in rows:\n",
    "                rows[r].remove(lamp)\n",
    "                if not rows[r]:\n",
    "                    del rows[r]\n",
    "\n",
    "            if c in cols:\n",
    "                cols[c].remove(lamp)\n",
    "                if not cols[c]:\n",
    "                    del cols[c]\n",
    "\n",
    "            if r+c in d1:\n",
    "                d1[r+c].remove(lamp)\n",
    "                if not d1[r+c]:\n",
    "                    del d1[r+c]\n",
    "\n",
    "            if r-c in d2:\n",
    "                d2[r-c].remove(lamp)\n",
    "                if not d2[r-c]:\n",
    "                    del d2[r-c]\n",
    "\n",
    "        def blockq(r, c):\n",
    "            if r in rows or c in cols or r+c in d1 or r-c in d2:\n",
    "                for sr in [-1,0,1]:\n",
    "                    for sc in [-1,0,1]:\n",
    "                        nr = r+sr\n",
    "                        nc = c+sc\n",
    "                        if 0<=nr<n and 0<=nc<n:\n",
    "                            lamp = (nr,nc)\n",
    "                            if lamp in lamps:\n",
    "                                close(lamp)\n",
    "                return 1\n",
    "            return 0\n",
    "\n",
    "        res = []\n",
    "\n",
    "        for query in queries:\n",
    "            r, c = query\n",
    "            res.append(blockq(r, c))\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gridIllumination(self, n: int, lamps: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        light = set()\n",
    "        row = defaultdict(set)\n",
    "        col = defaultdict(set)\n",
    "        left = defaultdict(set)\n",
    "        right = defaultdict(set)\n",
    "\n",
    "        for x,y in lamps:\n",
    "            light.add((x,y))\n",
    "            row[x].add(y)\n",
    "            col[y].add(x)\n",
    "            left[x+y].add((x,y))\n",
    "            right[x-y].add((x,y))\n",
    "        # print(\"light:\",light)\n",
    "        # print(\"row:\",row)\n",
    "        # print(\"col:\",col)\n",
    "        # print(\"left:\",left)\n",
    "        # print(\"right:\",right)\n",
    "        ans = []\n",
    "        for x,y in queries:\n",
    "            if x in row or y in col or x+y in left or x-y in right:\n",
    "                ans.append(1)\n",
    "            else:\n",
    "                ans.append(0)\n",
    "            for dx,dy in [(-1,-1),(-1,0),(-1,1),(0,-1),(0,0),(0,1),(1,-1),(1,0),(1,1)]:\n",
    "                nx,ny = x+dx,y+dy\n",
    "                if 0<=nx<n and 0<=ny<n and (nx,ny) in light:\n",
    "                    light.remove((nx,ny))\n",
    "                    #弹出行\n",
    "                    if nx in row and ny in row[nx]:\n",
    "                        row[nx].remove(ny)\n",
    "                        if not row[nx]:\n",
    "                            row.pop(nx)\n",
    "                    #弹出列\n",
    "                    if ny in col and nx in col[ny]:\n",
    "                        col[ny].remove(nx)\n",
    "                        if not col[ny]:\n",
    "                            col.pop(ny)\n",
    "                    #弹出左斜\n",
    "                    if nx+ny in left and (nx,ny) in left[nx+ny]:\n",
    "                        left[nx+ny].remove((nx,ny))\n",
    "                        if not left[nx+ny]:\n",
    "                            left.pop(nx+ny)\n",
    "                    #弹出右斜\n",
    "                    if nx-ny in right and (nx,ny) in right[nx-ny]:\n",
    "                        right[nx-ny].remove((nx,ny))\n",
    "                        if not right[nx-ny]:\n",
    "                            right.pop(nx-ny)\n",
    "        # print(\"light:\",light)\n",
    "        # print(\"row:\",row)\n",
    "        # print(\"col:\",col)\n",
    "        # print(\"left:\",left)\n",
    "        # print(\"right:\",right)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gridIllumination(self, n: int, lamps: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        light = set()\n",
    "        row = defaultdict(set)\n",
    "        col = defaultdict(set)\n",
    "        left = defaultdict(set)\n",
    "        right = defaultdict(set)\n",
    "\n",
    "        for x,y in lamps:\n",
    "            light.add((x,y))\n",
    "            row[x].add(y)\n",
    "            col[y].add(x)\n",
    "            left[x+y].add((x,y))\n",
    "            right[x-y].add((x,y))\n",
    "        # print(\"light:\",light)\n",
    "        # print(\"row:\",row)\n",
    "        # print(\"col:\",col)\n",
    "        # print(\"left:\",left)\n",
    "        # print(\"right:\",right)\n",
    "        ans = []\n",
    "        for x,y in queries:\n",
    "            if x in row or y in col or x+y in left or x-y in right:\n",
    "                ans.append(1)\n",
    "            else:\n",
    "                ans.append(0)\n",
    "            for dx,dy in [(-1,-1),(-1,0),(-1,1),(0,-1),(0,0),(0,1),(1,-1),(1,0),(1,1)]:\n",
    "                nx,ny = x+dx,y+dy\n",
    "                if 0<=nx<n and 0<=ny<n and (nx,ny) in light:\n",
    "                    light.remove((nx,ny))\n",
    "                    #弹出行\n",
    "                    if nx in row and ny in row[nx]:\n",
    "                        row[nx].remove(ny)\n",
    "                        if not row[nx]:\n",
    "                            row.pop(nx)\n",
    "                    #弹出列\n",
    "                    if ny in col and nx in col[ny]:\n",
    "                        col[ny].remove(nx)\n",
    "                        if not col[ny]:\n",
    "                            col.pop(ny)\n",
    "                    #弹出左斜\n",
    "                    if nx+ny in left and (nx,ny) in left[nx+ny]:\n",
    "                        left[nx+ny].remove((nx,ny))\n",
    "                        if not left[nx+ny]:\n",
    "                            left.pop(nx+ny)\n",
    "                    #弹出右斜\n",
    "                    if nx-ny in right and (nx,ny) in right[nx-ny]:\n",
    "                        right[nx-ny].remove((nx,ny))\n",
    "                        if not right[nx-ny]:\n",
    "                            right.pop(nx-ny)\n",
    "        # print(\"light:\",light)\n",
    "        # print(\"row:\",row)\n",
    "        # print(\"col:\",col)\n",
    "        # print(\"left:\",left)\n",
    "        # print(\"right:\",right)\n",
    "        return ans\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
